import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        // 把数组值所对应的坐标存起来
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        // 统计出现设置过的坐标
        List<Pair<Integer, Integer>> list = new LinkedList<>();
        queue.offer(new Pair<>(sr, sc));
        int m = image.length, n = image[0].length;
        while (!queue.isEmpty()) {
            Pair<Integer, Integer> pair = queue.poll();
            sr = pair.getKey();
            sc = pair.getValue();
            // 遍历四周是否出现了相同的颜色
            if (sr+1 < m && image[sr+1][sc] == image[sr][sc] && !list.contains(new Pair<>(sr+1, sc))) {
                queue.offer(new Pair<>(sr+1, sc));
            }
            if (sc+1 < n && image[sr][sc+1] == image[sr][sc] && !list.contains(new Pair<>(sr, sc+1))) {
                queue.offer(new Pair<>(sr, sc+1));
            }
            if (sr-1 >= 0 && image[sr-1][sc] == image[sr][sc] && !list.contains(new Pair<>(sr-1, sc))) {
                queue.offer(new Pair<>(sr-1, sc));
            }
            if (sc-1 >= 0 && image[sr][sc-1] == image[sr][sc] && !list.contains(new Pair<>(sr, sc-1))) {
                queue.offer(new Pair<>(sr, sc-1));
            }
            // 修改颜色
            image[sr][sc] = color;
            list.add(new Pair<>(sr, sc));
        }
        return image;
    }
}

class Pair<K, V> {
    private final K key;
    private final V value;

    /**
     * 构造一个新的Pair对象
     * @param key 键
     * @param value 值
     */
    public Pair(K key, V value) {
        // 注意：这里是进行初始化，是第一次赋值，而不是第二次赋值
        this.key = key;
        this.value = value;
    }

    /**
     * 获取键
     * @return 键
     */
    public K getKey() {
        return key;
    }

    /**
     * 获取值
     * @return 值
     */
    public V getValue() {
        return value;
    }
}